package dp;

//象棋中马的走法
//假设有一个9*10的棋盘  和目标点N  M  ，求马在给定N步内走到目标点的方法
//我们规定 可以走回头路 但是如果在还有剩余步数的情况下 已经到达终点 则不继续走
public class NumberOfJumpes {
    static final int N = 2;
    static final int M = 1;
    //a  b   为当前位置  k为剩余步数

    public static void main(String[] args) {
        System.out.println(getResult(0,0,5));
        System.out.println(getResDP(0,0,5));
    }

    //马在(a,b)位置，还有k步要走的方法数
    public static int getResult(int a,int b,int k){
        if (a < 0 || b<0 || a>9 || b>10){
            return 0;
        }
        if (a ==N && b==M) {
            return 1;
        }
        if (k==0){
            return 0;
        }
        int res = 0;
        //向右上走
        res += getResult(a+2,b+1,k-1);
        res += getResult(a+1,b+2,k-1);
        //向右下走
        res += getResult(a-2,b+1,k-1);
        res += getResult(a-1,b+2,k-1);
        //向左上走
        res += getResult(a+2,b-1,k-1);
        res += getResult(a+1,b-2,k-1);

        //向左下走
        res += getResult(a-2,b-1,k-1);
        res += getResult(a-1,b-2,k-1);
        return res;
     }

     //改动态规划
    public static int getResDP(int a,int b,int k){
        //可变参数为3个  需要准备三维数组
        //(a,b) 0-k
        int[][][] dp= new int[10][9][k+1];
        dp[a][b][0] = 1;    //k=0  代表已经走到终点
        for (int step=1;step <=k;step++ ){
            for (int i=0;i<10;i++){
                for (int j = 0;j<9;j++){
                    dp[i][j][step]
                            =getValue(dp,a+2,b+1,k-1)
                            +getValue(dp,a+1,b+2,k-1)
                            +getValue(dp,a-2,b+1,k-1)
                            +getValue(dp,a-1,b+2,k-1)
                            +getValue(dp,a+2,b-1,k-1)
                            +getValue(dp,a+1,b-2,k-1)
                            +getValue(dp,a-2,b-1,k-1)
                            +getValue(dp,a-1,b-2,k-1);
                }
            }
        }
        return dp[0][0][k];
    }

    public static int getValue(int[][][] dp,int a,int b,int k){
        if (a < 0 || b<0 || a>9 || b>10){  //越界
            return 0;
        }
        return dp[a][b][k];
    }
}
